#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/4/8 09:30|09:30
# @Author  : yangdingyi
# @File    : 面试题13. 机器人的运动范围.2020-04-08
# @Software: PyCharm


class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        import queue
        mm = [[0 for j in range(n)] for i in range(m)]
        ans = 1

        def test(x, y, k):
            ret = 0
            while x or y:
                ret += x % 10 + y % 10
                x //= 10
                y //= 10
            return ret <= k
        for i in range(m):
            for j in range(n):
                if test(i, j, k):
                    mm[i][j] = 1

        x, y = 0, 0
        step = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        mm[x][y] = 2
        # 深度优先

        def search(x, y):
            if x < 0 or x >=m or y <0 or y >=n:
                return
            for p in step:
                xx, yy = x + p[0], y + p[1]
                if 0 <= xx < m and 0 <= yy < n:
                    if mm[xx][yy] == 1:
                        mm[xx][yy] = 2
                        search(xx, yy)
        search(0, 0)
        ans = 0
        for i in range(m):
            for j in range(n):
                if mm[i][j] == 2:
                    ans += 1
        # 广度优先
        # que = queue.Queue()
        # que.put((x, y))
        # while que.qsize():
        #     item = que.get()
        #     x, y = item
        #     for p in step:
        #         xx, yy = x + p[0], y + p[1]
        #         if 0 <= xx < m and 0 <= yy < n:
        #             if mm[xx][yy] == 1:
        #                 mm[xx][yy] = 2
        #                 que.put((xx, yy))
        #                 ans += 1
        return ans


solve = Solution()
m0, n0, k0 = 2, 3, 1
print(m0, n0, k0)
print(solve.movingCount(m0, n0, k0))




